#include "linux_def.h"
#include "core.h"


static inline void rbtree_left_rotate(rbtree_node_t **root,
    rbtree_node_t *sentinel, rbtree_node_t *node);
static inline void rbtree_right_rotate(rbtree_node_t **root,
    rbtree_node_t *sentinel, rbtree_node_t *node);

void rbtree_insert(rbtree_t *tree, rbtree_node_t *node)
{
	rbtree_node_t	**root, *temp, *sentinel;

	root = (rbtree_node_t**)&tree->root;
	sentinel = tree->sentinel;

	if (*root == sentinel){
		node->parent = NULL;
		node->left = sentinel;
		node->right = sentinel;
		rbt_black(node);
		*root = node;
		return;
	}

	tree->insert(*root, node, sentinel);

	while (node != *root && rbt_is_red(node->parent)) {
		if (node->parent == node->parent->parent->left) {
			temp = node->parent->parent->right;
			if (rbt_is_red(temp)) {
				rbt_black(node->parent);
				rbt_black(temp);
				rbt_red(node->parent->parent);
				node = node->parent->parent;
			} else {
				if (node == node->parent->right) {
					node = node->parent;
					rbtree_left_rotate(root, sentinel, node);
				}
				rbt_black(node->parent);
				rbt_red(node->parent->parent);
				rbtree_right_rotate(root, sentinel, node->parent->parent);
			}
		} else {
			temp = node->parent->parent->left;
			if (rbt_is_red(temp)) {
				rbt_black(node->parent);
				rbt_black(temp);
				rbt_red(node->parent->parent);
				node = node->parent->parent;
			} else {
				if (node == node->parent->left) {
					node = node->parent;
					rbtree_right_rotate(root, sentinel, node);
				}

				rbt_black(node->parent);
				rbt_red(node->parent->parent);
				rbtree_left_rotate(root, sentinel, node->parent->parent);
			}
		}
	}

	rbt_black(*root);
}

void rbtree_insert_timer_value(rbtree_node_t *temp, rbtree_node_t *node, rbtree_node_t *sentinel)
{
	rbtree_node_t	**p;

	for (;;){
		p = ((int)node->key - (int)temp->key < 0) ? &temp->left : &temp->right;

		if (*p == sentinel)
			break;

		temp = *p;
	}

	*p = node;
	node->parent = temp;
	node->left = sentinel;
	node->right = sentinel;
	rbt_red(node);

	if (verbose)
		printf("%s, %d, %s\n", __FILE__, __LINE__, __func__);
}

void rbtree_delete(rbtree_t *tree, rbtree_node_t *node)
{
	uintptr_t	red;
	rbtree_node_t	**root, *sentinel, *subst, *temp, *w;

	root = (rbtree_node_t**)&tree->root;
	sentinel = tree->sentinel;

	if (node->left == sentinel){
		temp = node->right;
		subst = node;
	}else if (node->right == sentinel){
		temp = node->left;
		subst = node;
	}else{
		subst = rbtree_min(node->right, sentinel);

		if (subst->left != sentinel){
			temp = subst->left;
		}else{
			temp = subst->right;
		}
	}

	if (subst == *root){
		*root = temp;
		rbt_black(temp);
		return;
	}

	red = rbt_is_red(subst);
	if (subst == subst->parent->left){
		subst->parent->left = temp;
	}else{
		subst->parent->right = temp;
	}

	if (subst == node){
		temp->parent = subst->parent;
	}else{
		if (subst->parent == node){
			temp->parent = subst;
		}else{
			temp->parent = subst->parent;
		}

		subst->left = node->left;
		subst->right = node->right;
		subst->parent = node->parent;
		rbt_copy_color(subst, node);

		if (node == *root){
			*root = subst;
		}else{
			if (node == node->parent->left){
				node->parent->left = subst;
			}else{
				node->parent->right = subst;
			}
		}

		if (subst->left != sentinel){
			subst->left->parent = subst;
		}else{
			subst->right->parent = subst;
		}
	}

	if (red){
		return;
	}

	while (temp != *root && rbt_is_black(temp)){
		if (temp == temp->parent->left){
			w = temp->parent->right;

			if (rbt_is_red(w)){
				rbt_black(w);
				rbt_red(temp->parent);
				rbtree_left_rotate(root, sentinel, temp->parent);
				w = temp->parent->right;
			}

			if (rbt_is_black(w->left) && rbt_is_black(w->right)){
				rbt_red(w);
				temp = temp->parent;
			}else{
				if (rbt_is_black(w->right)){
					rbt_black(w->left);
					rbt_black(w);
					rbtree_right_rotate(root, sentinel, w);
					w = temp->parent->right;
				}

				rbt_copy_color(w, temp->parent);
				rbt_black(temp->parent);
				rbt_black(w->right);
				rbtree_left_rotate(root, sentinel, temp->parent);
				temp = *root;
			}
		}else{
			if (rbt_is_red(w)){
				rbt_black(w);
				rbt_red(temp->parent);
				rbtree_right_rotate(root, sentinel, temp->parent);
				w = temp->parent->left;
			}

			if (rbt_is_black(w->left) && rbt_is_black(w->right)){
				rbt_red(w);
				temp = temp->parent;
			}else{
				if (rbt_is_black(w->left)){
					rbt_black(w->right);
					rbt_black(w);
					rbtree_right_rotate(root, sentinel, w);
					w = temp->parent->left;
				}

				rbt_copy_color(w, temp->parent);
				rbt_black(temp->parent);
				rbt_black(w->left);
				rbtree_right_rotate(root, sentinel, temp->parent);
				temp = *root;
			}
		}
	}

	rbt_black(temp);
}


static inline void rbtree_left_rotate(rbtree_node_t **root, rbtree_node_t *sentinel, rbtree_node_t *node)
{
	rbtree_node_t  *temp;
	temp = node->right;
	node->right = temp->left;

	if (temp->left != sentinel) {
		temp->left->parent = node;
	}

	temp->parent = node->parent;
	if (node == *root) {
		*root = temp;
	} else if (node == node->parent->left) {
		node->parent->left = temp;
	} else {
		node->parent->right = temp;
	}

	temp->left = node;
	node->parent = temp;
}


static inline void rbtree_right_rotate(rbtree_node_t **root, rbtree_node_t *sentinel,rbtree_node_t *node)
{
	rbtree_node_t  *temp;
	temp = node->left;
	node->left = temp->right;
	if (temp->right != sentinel) {
		temp->right->parent = node;
	}
	temp->parent = node->parent;
	if (node == *root) {
		*root = temp;
	} else if (node == node->parent->right) {
		node->parent->right = temp;
	} else {
		node->parent->left = temp;
	}

	temp->right = node;
	node->parent = temp;
}

